/**
 * @file        unique_id_container.hpp
 * @brief       A container having a unique id for the elements. (no iterator)
 *
 * @author      Emre Turkay <emreturkay at gmail>
 * @date        Jul.17.2008
 *
 * Copyright Emre Turkay 2009
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file COPYRIGHT or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 */

#ifndef _UNIQUE_ID_CONTAINER_HPP_
#define _UNIQUE_ID_CONTAINER_HPP_

#include <algorithm>
#include <list>
#include <map>

/**
 * @brief A container having a unique id for the elements.
 * Provides an STL like interface.
 */
template <typename T>
struct unique_id_container
{
    /// Value type.
    typedef T value_type;
    /// Reference to the value type.
    typedef value_type& reference;
    /// Const reference to the value type.
    typedef const value_type& const_reference;
    /// The id type.
    typedef size_t id_type;
    /// The underlying container.
    typedef std::map<id_type, value_type> values_type;
    /// The type for the list of ids in order.
    typedef std::list<id_type> order_type;

    /// Empty default constructor.
    unique_id_container()
        : uuid_(0)
    {
    }

    /// Construct from a range.
    template <typename InputIterator>
    unique_id_container(InputIterator first, InputIterator last)
    {
        for (; first != last; ++first)
            push_back(*first);
    }

    /// Push back value (generates a unique id).
    void push_back(const_reference value)
    {
        id_type id = ++uuid_;
        values_[id] = value;
        order_.push_back(id);
    }

    /// Push front value (generates a unique id).
    void push_front(const_reference value)
    {
        id_type id = ++uuid_;
        values_[id] = value;
        order_.push_front(id);
    }

    /// Insert a value (id is a hint).
    void insert(id_type id, const_reference value)
    {
        id_type new_id = ++uuid_;
        values_[new_id] = value;
        order_type::iterator i = std::find(order_.begin(), order_.end(), id);
        order_.insert(i, new_id);
    }

    /// Insert a range of values, generates unique ids for each of them.
    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last)
    {
        for (; first != last; ++first)
            push_back(*first);
    }

    /// Returns the reference to the value of the given id.
    value_type& get(id_type id)
    {
        typename values_type::iterator i = values_.find(id);
        return i->second;
    }

    /// Returns the const reference to the value of the given id.
    const_reference get(id_type id) const
    {
        typename values_type::const_iterator i = values_.find(id);
        return i->second;
    }

    /// Returns the reference to the value of the given id via index operator.
    reference operator[](id_type id)
    {
        return get(id);
    }

    /// Returns the const reference to the value of the given id via index operator.
    const_reference operator[](id_type id) const
    {
        return get(id);
    }

    /// Returns the list of ids in order.
    order_type ids() const
    {
        return order_;
    }

    /// Returns the size of the container.
    size_t size() const
    {
        return order_.size();
    }

    /// Returns true if the container is empty, false otherwise.
    bool empty() const
    {
        return order_.empty();
    }

    /// Returns reference to the front value.
    reference front()
    {
        return get(order_.front());
    }

    /// Returns const reference to the front value.
    const_reference front() const
    {
        return get(order_.front());
    }

    /// Returns reference to the back value.
    reference back()
    {
        return get(order_.back());
    }

    /// Returns const reference to the back value.
    const_reference back() const
    {
        return get(order_.back());
    }

    /// Pops back the front value.
    void pop_front()
    {
        values_.erase(values_.find(order_.front()));
        order_.pop_front();
    }

    /// Pops back the back value.
    void pop_back()
    {
        values_.erase(values_.find(order_.back()));
        order_.pop_back();
    }

    /// Erases the value with the given id.
    void erase(id_type id)
    {
        values_.erase(values_.find(id));
        order_.erase(std::find(order_.begin(), order_.end(), id));
    }

    /// Clear the container.
    void clear()
    {
        values_.clear();
        order_.clear();
    }

    /// The id of the front item.
    id_type front_id() const
    {
        return order_.front();
    }

private:
    /// The unique id counter.
    id_type uuid_;
    /// The container for the values.
    values_type values_;
    /// The container for the ids.
    order_type order_;
};

#endif // _UNIQUE_ID_CONTAINER_HPP_
